1. Field of the Invention
The invention relates generally to the field of wireless communication. More particularly, the invention relates to a highly reliable, ad-hoc wireless mesh network and related methods of operation.
2. Description of the Related Art
Contemporary wireless communication networks (“networks”) typically allow simultaneous communication between several independently operating wireless devices. In order to provide the simultaneous communication, it is generally necessary to coordinate the communication so that the devices do not interfere with each other's transmissions and to ensure that devices sending and receiving messages are properly tuned and synchronized with respect to each other. Devices capable of interfering with each other's transmissions are referred to as adjacent devices.
In order for transmissions to be properly sent and received, it is important that no two adjacent devices transmit data over the same communication channel at the same time, an event referred to as a collision. Where two adjacent devices transmit data over the same communication channel at the same time, it typically results in interference, making it difficult for intended recipients of the transmissions to disentangle originally transmitted data.
A common approach used in radio frequency (RF) communication in an effort ensure that no two adjacent devices transmit over the same communication channel at the same time is to divide the available RF spectrum into fixed quanta called “frequency channels”, divide time into fixed quanta called “timeslots” which are aggregated into fixed groups called “frames”, and allow transmitters to send data using different frequency channels or different timeslots. An example of this type of communication is frequency hopping spread spectrum communication.
In a wireless network where both the RF spectrum and time are divided up, each separate combination of a particular “frequency channel” and a particular “timeslot” constitutes a unique “communication mode” that does not interfere with other communication modes in the network. Where the available RF spectrum is divided into many frequency channels and time is divided into many timeslots, each device in the network has a large number of non-interfering communication modes that it can use to communicate, thus making it possible for a large number of devices to participate in the network without interference. In addition, since the transmissions of two devices can only cause interference if the two devices are within RF range of one another, the likelihood of interference between devices can be further reduced by manipulating the spacing of the devices and the power level of the transmissions within a network.
Figure (FIG.) 1 illustrates a wireless communication network including a plurality of wireless devices “A” through “R”. Devices that are within RF range of each other (referred to as “adjacent devices”) have a line drawn between them. For example, devices “A”, “B”, and “C” are within RF range of each other. Hence, in order to ensure that transmissions involving devices “A”, “B”, or “C” are properly sent and received, no two of these devices may transmit on the same frequency channel during the same timeslot. In addition, in order for device “A” to successfully transmit data to devices “B” and “C” using a particular frequency channel and a particular timeslot, devices “B” and “C” must tune into the particular frequency channel during the particular timeslot in order to receive the message.
FIG. 2 illustrates an exemplary set of communication modes for a wireless network configuration. In FIG. 2, time is divided into sequential frames comprising 24 timeslots each, and the available RF spectrum is divided into 50 frequency channels. The beginning of a frame will be referred to as a “frame time” or a “synchronized time reference”. Each box in the grid shown in FIG. 2 represents one communication mode. For a particular frame of time, the number of available communication modes is the number of timeslots multiplied by the number of frequency channels, or in this case, 50*24=1200 modes.
Although dividing time and available RF bandwidth helps limit the amount of interference in a wireless network, it creates a complication for the devices of figuring out which frequency channels and timeslots the other devices are using. In order for a communication to succeed, a device transmitting data and a device receiving the transmitted data must both use the same timeslot and frequency channel. Since wireless networks often involve a large number of frequency channels and timeslots, the likelihood that a particular pair of devices will use the same frequency channel/timeslot combination by chance alone is very slim. As a result, it is useful for devices to coordinate their communications in some structured way. For example: networks that use timeslot assignment require mechanisms to synchronize the timing of adjacent transmitters and receivers to ensure successful communication.
In order to coordinate communications between adjacent devices, each device must be aware of the devices adjacent to it, i.e., the device's “adjacencies.” In some wireless networks, pre-planning may allow devices to be informed a priori of adjacent devices; however, in wireless networks where devices are added or removed dynamically, manual intervention or an automatic mechanism for discovering adjacent devices may be necessary. Automatic discovery of adjacent devices typically includes a bi-directional exchange of information between the adjacent devices that facilitates future coordinated communications.
In relatively small networks, communication of information between adjacent devices (such as devices A and B in FIG. 1) may be sufficient; however, in large networks, source and destination devices are often not adjacent and the information must traverse numerous intermediate devices to reach its final destination (for example, information sent from device A to device P in FIG. 1 must traverse numerous other devices). The process of moving information across multiple devices towards a final destination is referred to as “routing.”
Exemplary approaches used for routing include a priori planning (i.e., static routing), which is used when all device adjacencies within a network are fixed and known in advance, and various metric based approaches (i.e., dynamic routing), which is used in networks where device adjacencies change dynamically. The routing approach used in a particular network is generally chosen to suit the network's structure and the application performed by the network. For example, networks such as monitoring or control networks, where most information flows to or from a central point tend to use different routing approaches than networks such as peer-to-peer networks, where information flows between any two arbitrary devices.
Common properties used to characterize the performance of a routing method within a network include the method's ability to respond to dynamic changes in the network, its speed of delivery of information, the method's reliability of delivery, efficient use of network bandwidth, and efficient use of device resources (e.g. memory).
The quality of a communication link between two devices in a network may vary considerably in quality and may change abruptly. For example, a link that normally works well may become unreliable when an obstruction such as a large truck is introduced between the two devices forming the link. Moreover the quality of communication between an information source and destination separated by intermediate communication links varies with the quality of each intermediate communication link.
Certain routing methods are more reliable than others in the face of unreliable or rapidly changing intermediate links. Reliable routing methods are generally capable of quickly adapting to changing link quality and often send information along multiple simultaneous paths in order to increase the chances for proper delivery. Methods that send information along multiple simultaneous paths trade some network bandwidth and resource efficiency for increased reliability.
Network applications may attempt to compensate for lost network bandwidth and resource efficiency through efficient encoding of information. For example, the network applications may compress the information, or they may attempt to minimize the amount of overhead information sent.
For large RF monitoring and control networks, at least the above issues must be coordinated and balanced to yield a system that is reliable, efficient, and easy to maintain.
A conventional method of operating a wireless network to obtain reliable and efficient communication is described, for example, in U.S. Pat. No. 6,249,516 issued Jun. 19, 2001 to Brownrigg et al. (hereafter, “Brownrigg”). Brownrigg describes a method for transferring data between two communication networks of which one is a wireless network. To facilitate efficient and reliable communications, the bridging device maintains a map of paths within the wireless network to determine routes.
The map of paths stored in the bridging device must be updated as the quality and presence of network paths change. A central controller in the bridging device specifies an optimal path for data to traverse from each wireless device to the central controller. Due to the inherently dynamic nature of wireless networks and the interference to which they are subject, maintaining centralized path maps makes it both difficult and slow to respond to changes in the network, particularly when dealing with compromised links and large topologies.